package 栈队列与哈希表;

import java.util.Stack;

/**
 * 由于栈具有后进先出的特点，因此push和pop只需要对栈顶元素进行操作。
 * 如果使用上述的实现方式，只能访问到栈顶的元素，无法得到栈中最小的元素。
 * 当然，可以用另外一个变量来记录栈底的位置，通过遍历栈中所有的元素找出最小值，但是这种方法的时间复杂度为O（N），
 * 那么如何才能用O（1）的时间复杂度求出栈中最小的元素呢？在算法设计中，经常会采用空间来换取时间的方式来提高时间复杂度。
 * 也就是说，采用额外的存储空间来降低操作的时间复杂度。
 * 具体而言，在实现时使用两个栈结构，一个栈用来存储数据，另外一个栈用来存储栈的最小元素。
 * 实现思路如下：如果当前入栈的元素比原来栈中的最小值还小，则把这个值压入保存最小元素的栈中；
 * 在出栈时，如果当前出栈的元素恰好为当前栈中的最小值，保存最小值的栈顶元素也出栈，使得当前最小值变为当前最小值入栈之前的那个最小值。
 * 为了简单起见，可以在栈中保存int类型
 */
public class E如何用O1的时间复杂度求栈中最小元素 {

    //用来存储栈中元素
    private Stack<Integer> elemStack = new Stack<>();
    //栈顶永远存储当前elemStack中最小的值
    private Stack<Integer> minStack = new Stack<>();

    public void push(int data) {
        elemStack.push(data);
        //跟新保存最小元素的栈
        if (minStack.empty()) {
            minStack.push(data);
        } else {
            if (data < minStack.peek()) {
                minStack.push(data);
            }
        }
    }

    public int pop() {
        int topData = elemStack.peek();
        elemStack.pop();
        if (topData == min()) {
            minStack.pop();
        }
        return topData;
    }

    public int min() {
        if (minStack.empty()) {
            return Integer.MAX_VALUE;
        } else {
            return minStack.peek();
        }
    }

    public static void main(String[] args) {
        E如何用O1的时间复杂度求栈中最小元素 stack = new E如何用O1的时间复杂度求栈中最小元素();
        stack.push(5);
        System.out.println("栈中最小值为：" + stack.min());
        stack.push(6);
        System.out.println("栈中最小值为：" + stack.min());
        stack.push(2);
        System.out.println("栈中最小值为：" + stack.min());
        stack.pop();
        System.out.println("栈中最小值为：" + stack.min());


        // 1 2 3 4 5 6

    }
}
